package com.cherrish.demo.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cherrishccl
 * @time 2019-03-29 15:44
 * @name MaxSumSubSeq
 * @desc:
 */
public class MaxSumSubSeq {

    public static void main(String[] args) {
        int[] a = {-12, -11, -4, -13, -5, -32, 1, 6, 10};
        getMaxSumSeq(a);
    }

    /**
     * 最大子串和
     */
    private static void getMaxSumSeq(int[] a){
        int rmax = Integer.MIN_VALUE;
        int sum = Integer.MIN_VALUE;
        int  start = -1;
        int end = -1;
        int temp = -1;
        for(int i = 0; i < a.length; i++){
            if(sum > 0){
                sum += a[i];
            } else {
                sum = a[i];
                temp = i;
            }
            if(sum > rmax){
                start = temp;
                rmax = sum;
                end = i;
            }
        }
        for(int j = start; j <= end; j++){
            System.out.print(a[j] + " ");
        }
        System.out.println("nsum:" + rmax);
    }

    /**
     * 最大子串和
     */
    public static int maxSubArray(int[] arr) {
        int max = Integer.MIN_VALUE;
        int k = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if(k > 0){
                k += arr[i];
            }else{
                k = arr[i];
            }

            if(max < k){
                max = k;
            }
        }
        return max;
    }

    /**
     * 最大重复子串
     */
    public static String maxRepat(String input) {
        if(input == null || input.length() == 0){
            return null;
        }
        int max = Integer.MIN_VALUE;
        int k = Integer.MIN_VALUE;
        int first = 0;
        for (int i = 1; i < input.length(); i++) {
            for (int j = 0; j < input.length() - i; j++) {
                if(input.charAt(j) == input.charAt(i + j)){
                    k++;
                }else{
                    k = 0;
                }

                if(k > max){
                    max = k;
                    first = j - k + 1;
                }
            }
        }
        return input.substring(first, first + max);
    }

    /**
     * 最大无重复子串
     */
    public static int longestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int maxLength = 1;
        List<Character> list = new ArrayList<>();
        list.add(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            if (list.contains(s.charAt(i))) {
                int index = list.indexOf(s.charAt(i));
                list = list.subList(index + 1, list.size());
                list.add(s.charAt(i));
                maxLength = Math.max(maxLength, list.size());
            } else {
                list.add(s.charAt(i));
                maxLength = Math.max(maxLength, list.size());
            }
        }
        return maxLength;
    }
}
